home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / bplus20.zip / BPLUS.C < prev    next >
Text File  |  1989-04-24  |  26KB  |  994 lines
  1. /********************************************************************/
  2. /*                                                                  */
  3. /*             BPLUS file indexing program - Version 2.0            */
  4. /*                                                                  */
  5. /*                      A "shareware program"                       */
  6. /*                                                                  */
  7. /*                                                                  */
  8. /*                    Copyright (C) 1987-1989 by                    */
  9. /*                                                                  */
  10. /*                      Hunter and Associates                       */
  11. /*                      7900 Edgewater Drive                        */
  12. /*                      Wilsonville, Oregon  97070                  */
  13. /*                      (503) 694 - 1449                            */
  14. /*                                                                  */
  15. /********************************************************************/
  16.  
  17.  
  18. #include <stdio.h>
  19. #include <fcntl.h>
  20. #include <io.h>
  21. #include <sys\types.h>            /*  delete this line for Turbo C  */
  22. #include <sys\stat.h>
  23. #include <string.h>
  24. #include "bplus.h"
  25.  
  26.  
  27. /*  macros, constants, data types  */
  28.  
  29. #define  NULLREC      (-1L)
  30. #define  FREE_BLOCK   (-2)
  31.  
  32. #define  ENT_ADR(pb,off)  ((ENTRY*)((char*)((pb)->entries) + off))
  33. #define  ENT_SIZE(pe)     strlen((pe)->key) + 1 + 2 * sizeof(RECPOS)
  34. #define  BUFDIRTY(j)      (mci->cache[j].dirty)
  35. #define  BUFHANDLE(j)     (mci->cache[j].handle)
  36. #define  BUFBLOCK(j)      (mci->cache[j].mb)
  37. #define  BUFCOUNT(j)      (mci->cache[j].count)
  38. #define  CB(j)            (pci->pos[j].cblock)
  39. #define  CO(j)            (pci->pos[j].coffset)
  40. #define  TRUE             1
  41. #define  FALSE            0
  42.  
  43.                                     /* BPLUS uses the library routine    */
  44.                                     /* memmove which must be used with   */
  45.                     /* Turboc 1.5, 2.0, Quick C and      */
  46.                     /* MS C 5.0 and 5.1                  */
  47. /* #define memmove    memcpy */     /* Use this macro for Microsoft C4.0 */
  48.  
  49. /*  declare some global variables  */
  50.  
  51. IX_DESC      *pci;
  52. IX_BUFFER    bt_buffer;
  53. IX_BUFFER    *mci = &bt_buffer;
  54. BLOCK        *block_ptr;
  55. BLOCK        *spare_block;
  56. int          cache_ptr = 0;
  57. int          cache_init = 0;
  58. int          split_size = IXB_SPACE;
  59. int          comb_size  = (IXB_SPACE/2);
  60.  
  61. void pascal error(int, long);
  62. void pascal read_if(long, char *, int);
  63. void pascal write_if(int, long, char *, int);
  64. void pascal reset_buffers(IX_DESC *);
  65. int  pascal creat_if(char *);
  66. int  pascal open_if(char *);
  67. void pascal close_if(int);
  68. void pascal update_block(void);
  69. void pascal init_cache(void);
  70. int  pascal find_cache(RECPOS);
  71. int  pascal new_cache(void);
  72. void pascal load_cache(RECPOS);
  73. void pascal get_cache(RECPOS);
  74. void pascal retrieve_block(int, RECPOS);
  75. int  pascal prev_entry(int);
  76. int  pascal next_entry(int);
  77. void pascal copy_entry(ENTRY *, ENTRY *);
  78. int  pascal scan_blk(int);
  79. int  pascal last_entry(void);
  80. void pascal write_free( RECPOS, BLOCK *);
  81. RECPOS pascal get_free(void);
  82. int  pascal find_block(ENTRY *, int *, int *);
  83. void pascal movedown(BLOCK *, int, int);
  84. void pascal moveup(BLOCK *, int, int);
  85. void pascal ins_block(BLOCK *, ENTRY *, int);
  86. void pascal del_block(BLOCK *, int);
  87. void pascal split(int, ENTRY *, ENTRY *);
  88. void pascal ins_level(int, ENTRY *);
  89. int  pascal insert_ix(ENTRY *, IX_DESC *);
  90. int  pascal find_ix(ENTRY *, IX_DESC *, int);
  91. int  pascal combineblk(RECPOS, int);
  92. void pascal replace_entry(ENTRY *);
  93. void print_blk(BLOCK *);
  94.  
  95.  
  96. /*  file I/O for B-PLUS module  */
  97.  
  98. void pascal error(j, l)
  99.   int j;
  100.   long l;
  101.   {
  102.     static char *msg[3] = {"ERROR - CANNOT OPEN/CLOSE FILE",
  103.                            "ERROR WHILE READING FILE",
  104.                            "ERROR WHILE WRITING FILE"};
  105.     printf("\n  %s - Record Number %ld\n", msg[j], l);
  106.     exit(1);
  107.   } /* error */
  108.  
  109.  
  110. void pascal read_if(start, buf, nwrt)
  111.   long start;
  112.   char *buf;
  113.   int nwrt;
  114.   {
  115.     long err;
  116.     err = start - lseek(pci->ixfile, start, SEEK_SET);
  117.     if (err == 0) err = nwrt - read(pci->ixfile, buf, nwrt);
  118.     if (err != 0) error(1, start);
  119.   } /* read_if */
  120.  
  121.  
  122. void pascal write_if(handle, start, buf, nwrt)
  123.   int handle;
  124.   long start;
  125.   char *buf;
  126.   int nwrt;
  127.   {
  128.     long err;
  129.     err = start - lseek(handle, start, SEEK_SET);
  130.     if (err == 0) err = nwrt - write(handle, buf, nwrt);
  131.     if (err != 0) error(2, start);
  132.   } /* write_if */
  133.  
  134.  
  135. int pascal creat_if(fn)
  136.   char *fn;
  137.   {
  138.     int   ret;
  139.     ret = open(fn,O_RDWR|O_CREAT|O_TRUNC|O_BINARY,S_IWRITE);
  140.     if (ret  < 0) error(0,0L);
  141.     return (ret);
  142.   } /* creat_if */
  143.  
  144.  
  145. int pascal open_if(fn)
  146.   char *fn;
  147.   {
  148.     int  ret;
  149.     ret = open(fn,O_RDWR|O_BINARY);
  150.     if (ret < 1) error(0,0L);
  151.     return (ret);
  152.   } /* open_if */
  153.  
  154.  
  155. void pascal close_if(handle)
  156.   int handle;
  157.   {
  158.     if(close(handle) < 0)  error(2,0L);
  159.   } /*  close_if */
  160.  
  161.  
  162. int cdecl open_index(name, pix, dup)
  163.   char *name;
  164.   IX_DESC *pix;
  165.   int dup;
  166.   {
  167.     pci = pix;
  168.     pci->ixfile = open_if(name);
  169.     pci->root_dirty = FALSE;
  170.     pci->duplicate = dup;
  171.     read_if(0L,(char *)&(pix->root), (sizeof(BLOCK) + sizeof(IX_DISK)));
  172.     if (!cache_init)
  173.       {
  174.         init_cache();
  175.         cache_init = 1;
  176.       }
  177.     first_key(pix);
  178.     return ( IX_OK );
  179.   } /* open_index */
  180.  
  181.  
  182. void cdecl buffer_flush(pix)
  183.   IX_DESC *pix;
  184. {
  185.   int i;
  186.   if (pix->root_dirty)
  187.   {
  188.     write_if(pix->ixfile, 0L,(char *)&(pix->root),
  189.                (sizeof(BLOCK) + sizeof(IX_DISK)));
  190.     pix->root_dirty = FALSE;
  191.   }
  192.   for (i = 0; i < NUM_BUFS; i++)
  193.   {
  194.     if ( (BUFHANDLE(i) == pix->ixfile) && BUFDIRTY(i) )
  195.     {
  196.       write_if(BUFHANDLE(i),
  197.            BUFBLOCK(i).brec,
  198.            (char *) &BUFBLOCK(i),
  199.            sizeof(BLOCK));
  200.       BUFDIRTY(i) = FALSE;
  201.     }
  202.   }
  203. }
  204.  
  205. void pascal reset_buffers(pix)
  206.   IX_DESC *pix;
  207.   {
  208.     int i;
  209.     for (i = 0; i < NUM_BUFS; i++)
  210.       if (BUFHANDLE(i) == pix->ixfile) BUFBLOCK(i).brec = NULLREC;
  211.   }
  212.  
  213.  
  214. int cdecl close_index(pix)
  215.   IX_DESC *pix;
  216.   {
  217.     int ret = IX_OK;
  218.     buffer_flush(pix);
  219.     reset_buffers(pix);
  220.     close_if(pix->ixfile);
  221.     return( ret );
  222.   } /* close_index */
  223.  
  224.  
  225. int cdecl make_index(name, pix, dup)
  226.   char *name;
  227.   IX_DESC *pix;
  228.   int dup;
  229.   {
  230.     pci = pix;
  231.     pci->ixfile = creat_if(name);
  232.     pci->duplicate = dup;
  233.     pci->root_dirty = FALSE;
  234.     pci->dx.nl = 1;
  235.     pci->dx.ff = NULLREC;
  236.     pci->level = 0;
  237.     CO(0) = -1;
  238.     CB(0) = 0L;
  239.     pci->root.brec = 0L;
  240.     pci->root.bend = 0;
  241.     pci->root.p0 = NULLREC;
  242.     write_if(pci->ixfile, 0L,(char *)&(pix->root),
  243.                (sizeof(BLOCK) + sizeof(IX_DISK)));
  244.     if (!cache_init)
  245.       {
  246.         init_cache();
  247.         cache_init = 1;
  248.       }
  249.     first_key(pix);
  250.     return ( IX_OK );
  251.   } /* make_index */
  252.  
  253.  
  254. /*  cache I/O for BPLUS  */
  255.  
  256. void pascal update_block()
  257.   {
  258.     if (block_ptr == &(pci->root)) pci->root_dirty = TRUE;
  259.     else  BUFDIRTY(cache_ptr) = TRUE;
  260.   } /* update_block */
  261.  
  262.  
  263. void pascal init_cache()
  264.   {
  265.     register int  j;
  266.     for (j = 0; j < NUM_BUFS; j++)
  267.       {  BUFDIRTY(j) = 0;
  268.          BUFCOUNT(j) = 0;
  269.          BUFBLOCK(j).brec = NULLREC;
  270.       }
  271.   } /* init_cache */
  272.  
  273.  
  274. int pascal find_cache(r)
  275.   RECPOS r;
  276.   {
  277.     register int  j;
  278.     for (j = 0; j < NUM_BUFS; j++)
  279.       {
  280.         if((BUFBLOCK(j).brec == r) && (BUFHANDLE(j) == pci->ixfile))
  281.          {  cache_ptr = j;
  282.             return (1);
  283.       }  }
  284.     return (-1);
  285.   } /* find_cache */
  286.  
  287.  
  288. int pascal new_cache()
  289.   {
  290.     register int  i;
  291.     i = (cache_ptr + 1) % NUM_BUFS;
  292.     if (BUFDIRTY(i)) write_if(BUFHANDLE(i),
  293.                               BUFBLOCK(i).brec,
  294.                               (char *) &BUFBLOCK(i),
  295.                               sizeof(BLOCK));
  296.     BUFHANDLE(i) = pci->ixfile;
  297.     BUFDIRTY(i) = 0;
  298.     return (i);
  299.   } /* new_cache */
  300.  
  301.  
  302. void pascal load_cache(r)
  303.   RECPOS r;
  304.   {
  305.     cache_ptr = new_cache();
  306.     read_if(r, (char *)&BUFBLOCK(cache_ptr), sizeof(BLOCK));
  307.   } /* load_cache */
  308.  
  309.  
  310. void pascal get_cache(r)
  311.   RECPOS r;
  312.   {
  313.     if (find_cache(r) < 0)
  314.        load_cache(r);
  315.     block_ptr = &BUFBLOCK(cache_ptr);
  316.   } /* get_cache */
  317.  
  318.  
  319. void pascal retrieve_block(j, r)
  320.   int j;
  321.   RECPOS r;
  322.   {
  323.     if (j == 0)
  324.        block_ptr = &(pci->root);
  325.     else  get_cache(r);
  326.     CB(j) = block_ptr->brec;
  327.   } /* retrieve_block */
  328.  
  329.  
  330. /*  low level functions of BPLUS  */
  331.  
  332. int pascal prev_entry(off)
  333.   int off;
  334.   {
  335.      if (off <= 0)
  336.        {
  337.          off = -1;
  338.          CO(pci->level) = off;
  339.        }
  340.      else
  341.        off = scan_blk(off);
  342.      return(off);
  343.   } /* prev_entry */
  344.  
  345.  
  346. int pascal next_entry(off)
  347.   int off;
  348.   {
  349.      if (off == -1)
  350.        off = 0;
  351.      else
  352.        {
  353.          if (off < block_ptr->bend)
  354.             off += ENT_SIZE(ENT_ADR(block_ptr,off));
  355.        }
  356.      CO(pci->level) = off;
  357.      return (off);
  358.   } /* next_entry */
  359.  
  360.  
  361. void pascal copy_entry(to, from)
  362.   ENTRY *to;
  363.   ENTRY *from;
  364.   {
  365.     int me;
  366.     me = ENT_SIZE(from);
  367.     memcpy(to, from, me);
  368.   } /* copy_entry */
  369.  
  370.  
  371. int pascal scan_blk(n)
  372.   int n;
  373.   {
  374.      register int off, last;
  375.      off = 0;
  376.      last = -1;
  377.      while (off < n )
  378.        {  last = off;
  379.           off += ENT_SIZE(ENT_ADR(block_ptr,off));
  380.        }
  381.      CO(pci->level) = last;
  382.      return (last);
  383.   } /* scan_blk */
  384.  
  385.  
  386. int pascal last_entry()
  387.   {
  388.      return( scan_blk(block_ptr->bend) );
  389.   } /* last_entry */
  390.  
  391.  
  392. /*  maintain list of free index blocks  */
  393.  
  394. void pascal write_free(r, pb)
  395.   RECPOS r;
  396.   BLOCK *pb;
  397.   {
  398.     pb->p0 = FREE_BLOCK;
  399.     pb->brec = pci->dx.ff;
  400.     write_if(pci->ixfile, r, (char *) pb, sizeof(BLOCK));
  401.     pci->dx.ff = r;
  402.   } /* write_free */
  403.  
  404.  
  405. RECPOS pascal get_free()
  406.   {
  407.     RECPOS  r, rt;
  408.  
  409.     r = pci->dx.ff;
  410.     if ( r != NULLREC )
  411.       {  read_if(r, (char *)&rt, sizeof( RECPOS ));
  412.          pci->dx.ff = rt;
  413.       }
  414.     else
  415.       r = filelength (pci->ixfile);
  416.     return (r);
  417.   } /* get_free */
  418.  
  419.  
  420. /*  general BPLUS block level functions  */
  421.  
  422. int pascal find_block(pe, off, poff)
  423.   ENTRY *pe;
  424.   int *off;
  425.   int *poff;
  426.   {
  427.     register int pos, nextpos, ret;
  428.     pos = -1;
  429.     nextpos = 0;
  430.     ret = 1;
  431.     while ( nextpos < block_ptr->bend)
  432.       {
  433.         ret = strcmp((char *)(pe->key),
  434.                      (char *)(ENT_ADR(block_ptr, nextpos)->key));
  435.     if (ret <= 0) break;
  436.         pos = nextpos;
  437.     nextpos += ENT_SIZE(ENT_ADR(block_ptr,pos));
  438.     /* nextpos = next_entry(pos); */
  439.       }
  440.     *poff = pos;
  441.     if (ret == 0) *off = nextpos;
  442.     else *off = pos;
  443.     CO(pci->level) = *off;
  444.     return (ret);
  445.   } /* find_block */
  446.  
  447.  
  448. void pascal movedown(pb, off, n)
  449.   BLOCK *pb;
  450.   int off;
  451.   int n;
  452.   {
  453.     memmove(ENT_ADR(pb, off),
  454.            ENT_ADR(pb, off + n),
  455.            pb -> bend - (off + n));
  456.   } /* movedown */
  457.  
  458.  
  459. void pascal moveup(pb, off, n)
  460.   BLOCK *pb;
  461.   int off;
  462.   int n;
  463.   {
  464.     memmove(ENT_ADR(pb, off + n),
  465.             ENT_ADR(pb, off),
  466.             pb->bend - off);
  467.   } /* moveup */
  468.  
  469.  
  470. void pascal ins_block(pb, pe, off)
  471.   BLOCK *pb;
  472.   ENTRY *pe;
  473.   int off;
  474.   {
  475.     int size;
  476.     size = ENT_SIZE(pe);
  477.     moveup(pb,off,size);
  478.     copy_entry(ENT_ADR(pb,off),pe);
  479.     pb->bend += size;
  480.   } /* ins_block */
  481.  
  482.  
  483. void pascal del_block(pb, off)
  484.   BLOCK *pb;
  485.   int off;
  486.   {
  487.     int ne;
  488.     ne = ENT_SIZE(ENT_ADR(pb, off));
  489.     movedown(pb, off, ne);
  490.     pb->bend -= ne;
  491.   } /* del_block */
  492.  
  493.  
  494. /*  position at start/end of index  */
  495.  
  496. int cdecl first_key(pix)
  497.   IX_DESC *pix;
  498.   {
  499.     pci = pix;
  500.     block_ptr = &(pci->root);
  501.     CB(0) = 0L;
  502.     CO(0) = -1;
  503.     pci->level = 0;
  504.     while(block_ptr->p0 != NULLREC)
  505.       {
  506.         retrieve_block(++(pci->level), block_ptr->p0);
  507.         CO(pci->level) = -1;
  508.       }
  509.     return ( IX_OK );
  510.   } /* first_key */
  511.  
  512.  
  513. int cdecl last_key(pix)
  514.   IX_DESC *pix;
  515.   {
  516.     long  ads;
  517.     pci = pix;
  518.     block_ptr = &(pci->root);
  519.     CB(0) = 0L;
  520.     pci->level = 0;
  521.     if(last_entry() >= 0)
  522.       {
  523.         while ((ads = ENT_ADR(block_ptr,last_entry())->idxptr) != NULLREC)
  524.              retrieve_block(++(pci->level), ads);
  525.       }
  526.     CO(pci->level) = block_ptr->bend;
  527.     return ( IX_OK );
  528.   } /* last_key */
  529.  
  530.  
  531. /*  get next, previous entries  */
  532.  
  533. int cdecl next_key(pe, pix)
  534.   ENTRY *pe;
  535.   IX_DESC *pix;
  536.   {
  537.     RECPOS  address;
  538.     pci = pix;
  539.     retrieve_block(pci->level, CB(pci->level));
  540.     if(CO(pci->level) == -1) address = block_ptr->p0;
  541.     else
  542.      {
  543.        if (CO(pci->level) == block_ptr->bend) address = NULLREC;
  544.        else  address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  545.      }
  546.     while (address != NULLREC)
  547.       {
  548.          retrieve_block(++(pci->level), address);
  549.          CO(pci->level) = -1;
  550.          address = block_ptr->p0;
  551.       }
  552.     next_entry(CO(pci->level));
  553.     if (CO(pci->level) == block_ptr->bend)
  554.       {
  555.         do
  556.           { if(pci->level == 0)
  557.               {
  558.                 last_key(pci);
  559.                 return (EOIX);
  560.               }
  561.             --(pci->level);
  562.             retrieve_block(pci->level, CB(pci->level));
  563.             next_entry(CO(pci->level));
  564.           } while (CO(pci->level) == block_ptr->bend);
  565.       }
  566.     copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  567.     return ( IX_OK );
  568.   } /* next_key */
  569.  
  570.  
  571. int cdecl prev_key(pe, pix)
  572.   ENTRY *pe;
  573.   IX_DESC *pix;
  574.   {
  575.     RECPOS  address;
  576.     pci = pix;
  577.     retrieve_block(pci->level, CB(pci->level));
  578.     prev_entry(CO(pci->level));
  579.     if (CO(pci->level) == -1)
  580.       address = block_ptr->p0;
  581.     else
  582.       address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  583.     if (address != NULLREC)
  584.       { do
  585.           {
  586.             retrieve_block(++(pci->level), address);
  587.             address = ENT_ADR(block_ptr, last_entry())->idxptr;
  588.           } while (address != NULLREC);
  589.       }
  590.     if (CO(pci->level) == -1)
  591.       { do
  592.           {
  593.             if(pci->level == 0)
  594.               {
  595.                 first_key(pci);
  596.                 return (EOIX);
  597.               }
  598.             --(pci->level);
  599.           } while (CO(pci->level) == -1);
  600.         retrieve_block(pci->level, CB(pci->level));
  601.       }
  602.     copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  603.     return ( IX_OK );
  604.   } /* prev_key */
  605.  
  606.  
  607. /*  insert new entries into tree  */
  608.  
  609. void pascal split(l, pe, e)
  610.   int l;
  611.   ENTRY *pe;
  612.   ENTRY *e;
  613.   {
  614.     int  half, ins_pos, size;
  615.     ins_pos = CO(pci->level);
  616.     half = scan_blk(block_ptr->bend / 2 + sizeof(RECPOS));
  617.     if (half == ins_pos)
  618.       *e = *pe;
  619.     else
  620.       {
  621.          copy_entry(e, ENT_ADR(block_ptr, half));
  622.          size = ENT_SIZE(e);
  623.          movedown(block_ptr, half, size);
  624.          block_ptr->bend -= size;
  625.       }
  626.     spare_block = &BUFBLOCK(new_cache());
  627.     memmove(spare_block->entries,
  628.            ENT_ADR(block_ptr,half),
  629.            block_ptr->bend - half);
  630.     spare_block->brec = get_free();
  631.     spare_block->bend = block_ptr->bend - half;
  632.     spare_block->p0 = e->idxptr;
  633.     block_ptr->bend = half;
  634.     e->idxptr = spare_block->brec;
  635.     if (ins_pos < half)
  636.       ins_block(block_ptr,pe,ins_pos);
  637.     else if (ins_pos > half)
  638.       {
  639.          ins_pos -= ENT_SIZE(e);
  640.          ins_block(spare_block,pe,ins_pos - half);
  641.          CB(l) = e->idxptr;
  642.          CO(l) = CO(l) - half;
  643.       }
  644.     write_if(pci->ixfile, spare_block->brec,
  645.              (char *) spare_block, sizeof(BLOCK));
  646.   } /* split */
  647.  
  648.  
  649. void pascal ins_level(l, e)
  650.   int l;
  651.   ENTRY *e;
  652.   {
  653.     int  i;
  654.     if ( l < 0)
  655.       {  for (i = 1; i < MAX_LEVELS; i++)
  656.            {  CO(MAX_LEVELS - i) = CO(MAX_LEVELS - i - 1);
  657.               CB(MAX_LEVELS - i) = CB(MAX_LEVELS - i - 1);
  658.            }
  659.          memmove(spare_block, &(pci->root), sizeof(BLOCK));
  660.          spare_block->brec = get_free();
  661.          write_if(pci->ixfile, spare_block->brec,
  662.                   (char *) spare_block, sizeof(BLOCK));
  663.          pci->root.p0 = spare_block->brec;
  664.          copy_entry((ENTRY *) (pci->root.entries), e);
  665.          pci->root.bend = ENT_SIZE(e);
  666.          CO(0) = 0;
  667.          pci->level = 0;
  668.      (pci->dx.nl)++;
  669.      pci->root_dirty = TRUE;
  670.       }
  671.     else ins_block(block_ptr,e,CO(l));
  672.   } /* ins_level */
  673.  
  674.  
  675. int pascal insert_ix(pe, pix)
  676.   ENTRY *pe;
  677.   IX_DESC *pix;
  678.   {
  679.     ENTRY    e, ee;
  680.     int h;
  681.     h = 0;
  682.     pci = pix;
  683.     ee = *pe;
  684.     do
  685.       {
  686.          if(CO(pci->level) >= 0)
  687.            CO(pci->level) +=
  688.                   ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level)));
  689.          else
  690.            CO(pci->level) = 0;
  691.          update_block();
  692.          if( (block_ptr->bend + ENT_SIZE(&ee)) <= split_size)
  693.            {
  694.              ins_level(pci->level, &ee);
  695.              break;
  696.            }
  697.          else
  698.            {
  699.              h = 1;
  700.              split(pci->level,&ee, &e);
  701.               ee = e;
  702.               pci->level--;
  703.               if (pci->level < 0)
  704.                 {
  705.                   ins_level(pci->level, &e);
  706.                   break;
  707.                 }
  708.               retrieve_block(pci->level, CB(pci->level));
  709.            }
  710.       }
  711.     while (1);
  712.     if (h) find_ix(pe, pix, 0);
  713.     return ( IX_OK );
  714.   } /* insert_ix */
  715.  
  716.  
  717. /*  BPLUS find and add key functions  */
  718.  
  719. int pascal find_ix(pe, pix, find)
  720.   ENTRY *pe;
  721.   IX_DESC *pix;
  722.   int find;
  723.   {
  724.     int      level, off, poff, ret;
  725.     int      savelevel, saveoff, h;
  726.     RECPOS   ads, saveads;
  727.     pci = pix;
  728.     ads = 0L;
  729.     level = 0;
  730.     h = 0;
  731.     while (ads != NULLREC)
  732.       {  pci->level = level;
  733.          retrieve_block(level, ads);
  734.      if (find_block(pe, &off, &poff) == 0) ret = 1;
  735.      else ret = 0;
  736.      if (ret && find && !pci->duplicate) break;
  737.      if(ret && pci->duplicate)
  738.      {
  739.        saveads = ads;
  740.        savelevel = level;
  741.        saveoff = off;
  742.        off = poff;
  743.        h = 1;
  744.      }
  745.          if (off == -1)
  746.            ads = block_ptr->p0;
  747.          else
  748.        ads = ENT_ADR(block_ptr, off)->idxptr;
  749.          CO(level++) = off;
  750.        }
  751.      if (h && find)
  752.      {
  753.        if (!ret)
  754.        {
  755.      retrieve_block(savelevel, saveads);
  756.      pci->level = savelevel;
  757.      ret = 1;
  758.        }
  759.        CO(savelevel) = saveoff;
  760.      }
  761.      return ( ret );
  762.    } /* find_ix */
  763.  
  764.  
  765. int cdecl find_key(pe, pix)
  766.   ENTRY *pe;
  767.   IX_DESC *pix;
  768.   {
  769.     int ret;
  770.     ret = find_ix(pe, pix, 1);
  771.     if ( ret ) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  772.     return ( ret );
  773.   } /* find_key */
  774.  
  775.  
  776. int cdecl add_key(pe, pix)
  777.   ENTRY *pe;
  778.   IX_DESC *pix;
  779.   {
  780.     int ret;
  781.     ret = find_ix(pe, pix, 0);
  782.     if ( ret && (pci->duplicate == 0)) return ( IX_FAIL );
  783.     pe->idxptr = NULLREC;
  784.     return (insert_ix(pe, pix));
  785.   } /* add_key */
  786.  
  787.  
  788. int cdecl locate_key(pe, pix)
  789.   ENTRY *pe;
  790.   IX_DESC *pix;
  791.   {
  792.     int ret;
  793.     ret = find_ix(pe, pix, 1);
  794.     if (ret) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  795.     else if (next_key(pe,pix) == EOIX) ret = EOIX;
  796.     return ( ret );
  797.   } /* locate_key */
  798.  
  799.  
  800. int cdecl find_exact(pe, pix)
  801.   ENTRY *pe;
  802.   IX_DESC * pix;
  803.   {
  804.     int  ret;
  805.     ENTRY e;
  806.     copy_entry(&e, pe);
  807.     ret = find_key(&e, pix);
  808.     if ( ret && pci->duplicate)
  809.       {
  810.     while (e.recptr != pe->recptr)
  811.     {
  812.       if (next_key(&e, pci) == EOIX) return (0);   /* no more records */
  813.       if (strcmp(e.key, pe->key) != 0) return (0); /* key changed */
  814.     }
  815.       }
  816.     copy_entry(pe, &e);
  817.     return ( ret );
  818.   } /* find_exact */
  819.  
  820.  
  821. /* BPLUS delete key functions */
  822.  
  823. int cdecl delete_key(pe, pix)
  824.   ENTRY *pe;
  825.   IX_DESC *pix;
  826.   {
  827.      ENTRY   e;
  828.      RECPOS  ads;
  829.      int     h, leveli, levelf;
  830.      if (!find_exact(pe, pix))  return( IX_FAIL );
  831.      h = 1;
  832.      if ((ads = pe->idxptr) != NULLREC)
  833.        {
  834.           leveli = pci->level;
  835.           do
  836.             {
  837.                retrieve_block(++(pci->level), ads);
  838.                CO(pci->level) = -1;
  839.             }
  840.           while ((ads = block_ptr->p0) != NULLREC);
  841.           CO(pci->level) = 0;
  842.           copy_entry(&e, ENT_ADR(block_ptr, CO(pci->level)));
  843.           levelf = pci->level;
  844.           pci->level = leveli;
  845.           replace_entry(&e);
  846.           pci->level = levelf;
  847.        }
  848.      while ( h )
  849.        {
  850.           retrieve_block(pci->level, CB(pci->level));
  851.           del_block(block_ptr, CO(pci->level));
  852.           update_block();
  853.           if ( (pci->level == 0) && (block_ptr->bend == 0))
  854.           /* tree was reduced in height */
  855.             {
  856.               if (pci->root.p0 != NULLREC)
  857.                 {
  858.                   retrieve_block(++pci->level, pci->root.p0);
  859.                   memmove(&(pci->root), block_ptr, sizeof(BLOCK));
  860.                   (pci->dx.nl)--;
  861.                   write_free(block_ptr->brec, block_ptr);
  862.                   BUFDIRTY(cache_ptr) = 0;
  863.                   BUFHANDLE(cache_ptr) = 0;
  864.                 }
  865.               break;
  866.             }
  867.           h = (block_ptr->bend < comb_size) && (pci->level > 0);
  868.           if ( h )
  869.               h = combineblk(CB(pci->level), block_ptr->bend);
  870.        }
  871.     find_ix(pe,pix,0);
  872.     return( IX_OK );
  873.   } /* delete_key */
  874.  
  875.  
  876. int pascal combineblk(ads, size)
  877.   RECPOS ads;
  878.   int size;
  879.   {
  880.     ENTRY  e;
  881.     RECPOS address;
  882.     int    esize, off, ret, saveoff, ibuff;
  883.     ret = 0;
  884.     saveoff = CO(--(pci->level));
  885.     retrieve_block(pci->level, CB(pci->level));
  886.     if ((off = next_entry( saveoff )) < block_ptr->bend)
  887.       /* combine with page on right */
  888.       {
  889.         if ( (ENT_SIZE(ENT_ADR(block_ptr, off)) + size) < split_size)
  890.           {
  891.             copy_entry(&e, ENT_ADR(block_ptr, off));
  892.             address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  893.             retrieve_block(++pci->level, address);
  894.             ibuff = cache_ptr;
  895.             spare_block = block_ptr;
  896.             retrieve_block(pci->level, ads);
  897.             esize = ENT_SIZE(&e);
  898.             if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
  899.                  && (spare_block->bend <= block_ptr->bend + esize))
  900.                return( ret );
  901.             e.idxptr = spare_block->p0;
  902.             ins_block(block_ptr, &e, block_ptr->bend);
  903.             update_block();
  904.             if ((block_ptr->bend + spare_block->bend) < split_size)
  905.             /* combine the blocks */
  906.               {
  907.                 memmove(ENT_ADR(block_ptr, block_ptr->bend),
  908.                        ENT_ADR(spare_block, 0),
  909.                        spare_block->bend);
  910.                 block_ptr->bend += spare_block->bend;
  911.                 write_free(spare_block->brec, spare_block);
  912.                 BUFDIRTY(ibuff) = 0;
  913.                 BUFHANDLE(ibuff) = 0;
  914.                 --pci->level;
  915.                 ret = 1;
  916.               }
  917.             else
  918.             /* move an entry up to replace the one moved */
  919.               {
  920.                 copy_entry(&e, ENT_ADR(spare_block, 0));
  921.                 esize = ENT_SIZE(&e);
  922.                 movedown(spare_block, 0, esize);
  923.                 spare_block->bend -= esize;
  924.                 spare_block->p0 = e.idxptr;
  925.                 BUFDIRTY(ibuff) = 1;
  926.                 --(pci->level);
  927.                 replace_entry(&e);
  928.               }
  929.           }
  930.       }
  931.     else
  932.       /* move from page on left */
  933.       {
  934.         if ( (ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level))) + size)
  935.                  < split_size)
  936.           {
  937.             copy_entry(&e, ENT_ADR(block_ptr, saveoff));
  938.             off = prev_entry(saveoff);
  939.             if (CO(pci->level) == -1) address = block_ptr->p0;
  940.             else address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  941.             retrieve_block(++pci->level, address);
  942.             off = last_entry();
  943.             ibuff = cache_ptr;
  944.             spare_block = block_ptr;
  945.             retrieve_block(pci->level, ads);
  946.             esize = ENT_SIZE(&e);
  947.             if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
  948.                  && (spare_block->bend <= block_ptr->bend + esize))
  949.                return( ret );
  950.             BUFDIRTY(ibuff) = 1;
  951.             CO(pci->level) = 0;
  952.             e.idxptr = block_ptr->p0;
  953.             ins_block(block_ptr, &e, 0);
  954.             if ((block_ptr->bend + spare_block->bend) < split_size)
  955.             /* combine the blocks */
  956.               {
  957.                 memmove(ENT_ADR(spare_block, spare_block->bend),
  958.                        ENT_ADR(block_ptr, 0),
  959.                        block_ptr->bend);
  960.                 spare_block->bend += block_ptr->bend;
  961.                 write_free(block_ptr->brec, block_ptr);
  962.                 BUFDIRTY(cache_ptr) = 0;
  963.                 BUFHANDLE(cache_ptr) = 0;
  964.                 CO(--(pci->level)) = saveoff;
  965.                 ret = 1;
  966.               }
  967.             else
  968.             /* move an entry up to replace the one moved */
  969.               {
  970.                  block_ptr->p0 = ENT_ADR(spare_block,off)->idxptr;
  971.                  copy_entry(&e, ENT_ADR(spare_block, off));
  972.                  spare_block->bend = off;
  973.                  update_block();
  974.                  CO(--(pci->level)) = saveoff;
  975.                  replace_entry(&e);
  976.               }
  977.           }
  978.       }
  979.     return ( ret );
  980.   } /* combineblk */
  981.  
  982.  
  983. void pascal replace_entry(pe)
  984.   ENTRY *pe;
  985.   {
  986.     retrieve_block(pci->level, CB(pci->level));
  987.     pe->idxptr = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  988.     del_block(block_ptr, CO(pci->level));
  989.     prev_entry(CO(pci->level));
  990.     insert_ix(pe, pci);
  991.     update_block();
  992.   } /* replace_entry */
  993.  
  994.